package com.extra;

import java.util.*;

public class Solution841 {
    public boolean canVisitAllRoomsBFS(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];
        visited[0] = true;
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
        while (!list.isEmpty()) {
            int key = list.removeFirst();
            for (int x : rooms.get(key)) {
                if (visited[x]) continue;
                visited[x] = true;
                list.add(x);
            }
        }
        for (boolean b : visited) {
            if (!b) return false;
        }
        return true;
    }

    public boolean canVisitAllRoomsDFS(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];
        dfs(visited, 0, rooms);
        for (boolean b : visited) {
            if (!b) return false;
        }
        return true;
    }

    public void dfs(boolean[] visited, int key, List<List<Integer>> rooms) {
        visited[key] = true;
        for (int x : rooms.get(key)) {
            if (!visited[x]) dfs(visited, x, rooms);
        }
    }
}
